package bintree.LeetCode;

import java.util.*;

//94. 二叉树的中序遍历——左右根

//public class Num94_inorder {
//    List<Integer> rep = new ArrayList<>();
//    public List<Integer> inorderTraversal(TreeNode root) {
//        if(root == null){
//            return rep;
//        }
//        inorderTraversal(root.left);
//        rep.add(root.val);
//        inorderTraversal(root.right);
//        return rep;
//    }
//}

//中序遍历非递归写法
public class Num94_inorder {

    public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> ret = new ArrayList<>();
       if(root == null){
           return ret;
       }
        Deque<TreeNode> stack = new ArrayDeque<>();//这是基于动态数组实现的，也可以用原来的栈，一样的。
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            //先一路向左走到低
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }//————左
            //cur此时已经为空，弹出栈顶元素，就是第一个左子树为空的节点
            cur = stack.pop();//————跟
            ret.add(cur.val);
            //继续访问右子树开始搜索
            cur = cur.right;//————右
        }

        return ret;
    }

}
